import java.io.File;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * Generates parsing table from parser grammar.
 * 
 * @author Chen Chen
 * 
 */
public class ParserGenerator {
        String startSymbol = null;
        public List<ProductionRule> stmts = new ArrayList<ProductionRule>();
        Map<String, Set<String>> firstSets = new HashMap<String, Set<String>>();
        Map<String, Set<String>> followSets = new HashMap<String, Set<String>>();
        ParsingTable parsingtable = new ParsingTable();
        List<String> tokens = new ArrayList<String>();
        List<String> nonterminals = new ArrayList<String>();

        public ParserGenerator(File input) throws Exception {

                Scanner sc = new Scanner(input);
                boolean foundStartSymbol = false;
                // read headers

                while (sc.hasNextLine()) {
                        String nextline = sc.nextLine().trim();
                        if (nextline.length() > 0)
                                if (nextline.charAt(0) == '%') {
                                        Scanner wordreader = new Scanner(nextline);
                                        String type = wordreader.next().substring(1);
                                        if (type.equalsIgnoreCase("tokens"))
                                                while (wordreader.hasNext())
                                                        tokens.add(wordreader.next());
                                        else if (type.equalsIgnoreCase("non-terminals"))
                                                while (wordreader.hasNext())
                                                        nonterminals.add(wordreader.next());
                                        else if (type.equalsIgnoreCase("start"))
                                                startSymbol = wordreader.next();
                                        else if (type.equalsIgnoreCase("rules"))
                                                break;
                                }

                }

                // create list of production rule from input string

                while (sc.hasNextLine()) {
                        String line = sc.nextLine().trim();

                        if (line.length() > 0)
                                stmts.add(new ProductionRule(line));
                }

                System.out.println("finish reading");
                removeLeftRecursion();
					 leftFactor();
                getFirstSets();
                getFollowSets();
                getParsingTable();
                System.out.println("start sym " + startSymbol);

        }
		  
		  private void leftFactor() throws Exception {
		  			 boolean modified = true;
		
					 while (modified) {
					 		modified = false;
							List<ProductionRule> tmpcopy = new ArrayList<ProductionRule>();
							 for (ProductionRule stmt: stmts) {
					 		tmpcopy.add(stmt);
							}
							for (ProductionRule stmt : tmpcopy) {
								String lhs = stmt.leftHandSide;
								List<List<String>> rhs = stmt.rightHandSide;
								for(int i = 0; i < rhs.size(); i++) {
	
									for(int j = i + 1; j < rhs.size(); j++) {
										System.out.println(stmt.toString());
										System.out.println(rhs.get(i).get(0) + " % " + rhs.get(j).get(0));
										
										if(rhs.get(i).get(0).equals(rhs.get(j).get(0))) {
											modified = true;
											System.out.println("check");
											List<String> tmp1 = rhs.get(i);
											List<String> tmp2 = rhs.get(j);
											rhs.remove(tmp1);
											rhs.remove(tmp2);
											StringBuilder sb = new StringBuilder();
											sb.append(lhs);
											sb.deleteCharAt(lhs.length() - 1);
											sb.append("'>");
											String newlhs = sb.toString();
											List<String> tmplist = new ArrayList<String>();
											tmplist.add(tmp1.get(0));
											tmplist.add(newlhs);
											rhs.add(tmplist);
											StringBuilder newrhsbuilder = new StringBuilder();
											tmp1.remove(tmp1.get(0));
											tmp2.remove(tmp2.get(0));
											if(tmp1.size() == 0) {
												tmp1.add("EPSILON");
											}
											if(tmp2.size() == 0) {
												tmp2.add("EPSILON");
											}
											for(String str : tmp1) {
												newrhsbuilder.append(str + " ");
											}
											newrhsbuilder.append("| ");
											for(String str : tmp2) {
												newrhsbuilder.append(str + " ");
											}
											System.out.println(tmp1 + " ^ tmp1");
											System.out.println(tmp2 + " ^ tmp2");
											
											String newrhs = newrhsbuilder.toString();
											
											ProductionRule newRule = new ProductionRule(newlhs + " : " + newrhs);
											stmts.add(newRule);
										}
									}
								}
							}
						}
					}
											
									
										
									
							
					 	

        private void removeLeftRecursion() throws Exception {
                boolean modified = true;
                while (modified) {
                        modified = false;
                        for (ProductionRule stmt : stmts) {
                                List<List<String>> leftRecursionList = new ArrayList<List<String>>();
                                List<List<String>> nonRecursionList = new ArrayList<List<String>>();
                                for (List<String> e : stmt.rightHandSide) {
                                        if (e.get(0).trim().equals(stmt.leftHandSide.trim()))
                                                leftRecursionList.add(e);
                                        else
                                                nonRecursionList.add(e);
                                }
                                if (leftRecursionList.size() > 0) {
                                        stmts.remove(stmt);
                                        // construct new statements
                                        StringBuilder stmt1 = new StringBuilder();// A -> v_1A' |
                                                                                                                                // v_2A' | ... |
                                                                                                                                // v_mA'
                                        stmt1.append(stmt.leftHandSide + " : ");
                                        for (List<String> e : nonRecursionList) {
                                                for (String t : e) {
                                                        stmt1.append(' ');
                                                        stmt1.append(t);
                                                        stmt1.append(' ');
                                                }
                                                stmt1.append(stmt.leftHandSide.substring(0,
                                                                stmt.leftHandSide.length() - 1) + "'" + ">");
                                                stmt1.append(" | ");

                                        }
                                        stmt1.delete(stmt1.length() - 2, stmt1.length());

                                        StringBuilder stmt2 = new StringBuilder();// A' -> u_1A' |
                                                                                                                                // u_2A'| ... |
                                                                                                                                // u_nA' |
                                                                                                                                // epsilon
                                        stmt2.append(stmt.leftHandSide.substring(0,
                                                        stmt.leftHandSide.length() - 1) + "'" + "> : ");
                                        for (List<String> e : leftRecursionList) {
                                                for (int i = 1; i < e.size(); i++) {
                                                        stmt2.append(' ');
                                                        stmt2.append(e.get(i));
                                                        stmt2.append(' ');
                                                }
                                                stmt2.append(stmt.leftHandSide.substring(0,
                                                                stmt.leftHandSide.length() - 1) + "'" + ">");
                                                stmt2.append(" | ");
                                        }
                                        stmt2.append("EPSILON");

                                        stmts.add(new ProductionRule(stmt1.toString()));
                                        stmts.add(new ProductionRule(stmt2.toString()));
                                        modified = true;
                                        break;
                                }
                        }
                }

        }

        /**
         * returns a set of the symbols in the grammar
         * 
         * @return a set of the symbols in the grammar
         */
        private Set<String> getGrammarSymbols() {
                Set<String> symbols = new HashSet<String>();
                for (ProductionRule stmt : stmts) {
                        symbols.add(stmt.leftHandSide);
                        for (List<String> e : stmt.rightHandSide)
                                symbols.addAll(e);
                }
                return symbols;
        }

        /**
         * returns a set of the non-terminals in the grammar
         * 
         * @return a set of the non-terminals in the grammar
         */
        public Set<String> getNonterminals() {
                Set<String> symbols = new HashSet<String>();
                for (ProductionRule stmt : stmts) {
                        symbols.add(stmt.leftHandSide);
                        for (List<String> e : stmt.rightHandSide)
                                for (String s : e)
                                        if (!isTerminal(s))
                                                symbols.add(s);
                }
                return symbols;
        }

        /**
         * returns a set of terminals in the grammar
         * 
         * @return a set of terminals in the grammar
         */
        private Set<String> getTerminals() {
                Set<String> symbols = new HashSet<String>();
                for (ProductionRule stmt : stmts) {
                        symbols.add(stmt.leftHandSide);
                        for (List<String> e : stmt.rightHandSide)
                                for (String s : e)
                                        if (isTerminal(s))
                                                symbols.add(s);
                }
                return symbols;
        }

        /**
         * updates the first set of one symbol x given the first sets of all symbols
         * 
         * @param x
         *            symbol whose first set to be updated
         * @param firstsets
         *            first sets of all symbols
         * @return if any changes are made
         */
        private boolean updateFirstSet(String x, Map<String, Set<String>> firstsets) {
                Set<String> firstset = firstsets.get(x);
                boolean modified = false;
                if (!isTerminal(x)) // non-terminal
                        for (ProductionRule stmt : stmts)
                                if (stmt.leftHandSide.equals(x.trim())) // production rule
                                                                                                                // X->X_1X_2...X_n
                                        for (List<String> e : stmt.rightHandSide)
                                                for (int i = 0; i < e.size(); i++) {
                                                        Set<String> tmpset = firstsets.get(e.get(i));
                                                        boolean hasEpsilon = tmpset.contains("EPSILON");
                                                        for (String s : tmpset)
                                                                // First(x)=First(x_i)-{EPSILON}
                                                                if (!s.equals("EPSILON"))
                                                                        modified = modified || firstset.add(s);

                                                        if (!hasEpsilon)// first(x_i) does not contain
                                                                                        // epsilon, then first(x) does not
                                                                                        // contain first(x_{i+1})
                                                                break;
                                                        else if (i == e.size() - 1)// if all contain
                                                                                                                // epsilon, then
                                                                                                                // first(x) contains
                                                                                                                // epsilon
                                                                modified = modified || firstset.add("EPSILON");
                                                }

                return modified;
        }

        /**
         * checks if a symbol is a terminal
         * 
         * @param x
         *            symbol to be checked
         * @return if a symbol is a terminal
         */
        public boolean isTerminal(String x) {

                return (x.charAt(0) != '<') || (x.charAt(x.length() - 1) != '>');
        }

        /**
         * gets the first sets of all terminals
         * 
         * @return a map maps each symbol to its first set
         */
        public Map<String, Set<String>> getFirstSets() {

                for (String symbol : getGrammarSymbols()) {
                        Set<String> tmpset = new HashSet<String>();
                        if (isTerminal(symbol))
                                tmpset.add(symbol);
                        firstSets.put(symbol, tmpset);
                }
                boolean modified = true;
                while (modified) {
                        modified = false;
                        for (String t : firstSets.keySet())
                                modified = modified || updateFirstSet(t, firstSets);

                }
                return firstSets;
        }

        /**
         * Gets the first set of a sequence of symbols.
         * 
         * @param x
         *            a sequence of symbols
         * @return the first set of x
         */
        public Set<String> getFirstSet(List<String> x) {
                Set<String> firstset = new HashSet<String>();
                for (int i = 0; i < x.size(); i++) {
                        firstset.addAll(firstSets.get(x.get(i)));
                        if (!firstSets.get(x.get(i)).contains("EPSILON"))
                                break;
                        else if (i == x.size() - 1)
                                firstset.add("EPSILON");
                }
                return firstset;
        }

        /**
         * update the follow sets for non-terminals
         * 
         * @return a map maps non-terminals to their follow sets
         */
        public Map<String, Set<String>> getFollowSets() {
                for (String t : getNonterminals())
                        if (t.equals(startSymbol)) {
                                HashSet<String> tmpset = new HashSet<String>();
                                tmpset.add("$");
                                followSets.put(t, tmpset);
                        } else
                                followSets.put(t, new HashSet<String>());

                boolean modified = true;
                while (modified) {
                        modified = false;
                        for (ProductionRule stmt : stmts)
                                for (List<String> e : stmt.rightHandSide)
                                        for (int i = 0; i < e.size(); i++) {
                                                if (!isTerminal(e.get(i))) {
                                                        List<String> list = new ArrayList<String>();
                                                        for (int j = i + 1; j < e.size(); j++)
                                                                list.add(e.get(j));
                                                        Set<String> tmpset = getFirstSet(list);
                                                        boolean hasEpsilon = tmpset.remove("EPSILON")
                                                                        || i == e.size() - 1;
                                                        modified = modified
                                                                        || followSets.get(e.get(i)).addAll(tmpset);
                                                        if (hasEpsilon)
                                                                modified = modified
                                                                                || followSets
                                                                                                .get(e.get(i))
                                                                                                .addAll(followSets
                                                                                                                .get(stmt.leftHandSide));
                                                }
                                        }

                }

                return followSets;
        }

        /**
         * computes parsing table
         * 
         * @return parsing table
         * @throws Exception
         */
        public ParsingTable getParsingTable() throws Exception {
                for (ProductionRule stmt : stmts) {
                        String A = stmt.leftHandSide;
                        for (List<String> rule : stmt.rightHandSide) {
                                String tmprhs = "";
                                for (String s : rule)
                                        tmprhs += s + " ";
                                Set<String> tmpfirstset = getFirstSet(rule);
                                for (String a : tmpfirstset)
                                        parsingtable.set(A, a, new ProductionRule(A + " : "
                                                        + tmprhs.trim()));

                                if (tmpfirstset.contains("EPSILON")) {
                                        for (String a : followSets.get(A))
                                                parsingtable.set(A, a, new ProductionRule(A + " : "
                                                                + tmprhs.trim()));

                                }
                        }
                }
                return parsingtable;
        }
}

